5.5 Buscar o localizar un elemento de una lista doblemente enlazada:  

En muchos aspectos, una lista doblemente enlazada se comporta como dos listas abiertas que comparten los datos. En ese sentido, todo lo dicho en el capítulo sobre la localización de elementos en listas abiertas se puede aplicar a listas doblemente enlazadas.

Pero además tenemos la ventaja de que podemos avanzar y retroceder desde cualquier nodo, sin necesidad de volver a uno de los extremos de la lista.

Por supuesto, se pueden hacer listas doblemente enlazadas no ordenadas, existen cientos de problemas que pueden requerir de este tipo de estructuras. Pero parece que la aplicación más sencilla de listas doblemente enlazadas es hacer arrays dinámicos ordenados, donde buscar un elemento concreto a partir de cualquier otro es más sencillo que en una lista abierta corriente.

Pero de todos modos veamos algún ejemplo sencillo.

Para recorrer una lista procederemos de un modo parecido al que usábamos con las listas abiertas, ahora no necesitamos un puntero auxiliar, pero tenemos que tener en cuenta que Lista no tiene por qué estar en uno de los extremos:

1. Retrocedemos hasta el comienzo de la lista, asignamos a lista el valor de lista->anterior mientras lista->anterior no sea NULL.
2. Abriremos un bucle que al menos debe tener una condición, que el índice no sea NULL.
3. Dentro del bucle asignaremos a lista el valor del nodo siguiente al actual.

Por ejemplo, para mostrar todos los valores de los nodos de una lista, podemos usar el siguiente bucle en C:

typedef struct _nodo {
  int dato;
  struct _nodo *siguiente;
  struct _nodo *anterior;
  } tipoNodo;
  
  typedef tipoNodo *pNodo;
  typedef tipoNodo *Lista;
  ...
  pNodo = indice;
  ...
  indice = Lista;
  while(indice->anterior) indice = indice->anterior;
  while(indice) {
     printf("%d\n", indice->dato);
     indice = indice->siguiente;
  }
  ...

Es importante que no perdamos el nodo Lista, si por error le asignáramos un valor de un puntero a un nodo que no esté en la lista, no podríamos acceder de nuevo a ella.

Es por eso que tendremos especial cuidado en no asignar el valor NULL a Lista.

5.6 Eliminar un elemento de una lista doblemente enlazada:  

Analizaremos tres casos diferentes:

1. Eliminar el único nodo de una lista doblemente enlazada.
2. Eliminar el primer nodo.
3. Eliminar el último nodo.
4. Eliminar un nodo intermedio.

Para los casos que lo permitan consideraremos dos casos: que el nodo a eliminar es el actualmente apuntado por Lista o que no.

Eliminar el único nodo en una lista doblemente enlazada:

En este caso, ese nodo será el apuntado por Lista.

1. Eliminamos el nodo.
2. Hacemos que Lista apunte a NULL.

Eliminar el primer nodo de una lista doblemente enlazada:

Tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->siguiente.

1. Si nodo apunta a Lista, hacemos que Lista apunte a Lista->siguiente.
2. Hacemos que nodo->siguiente->anterior apunte a NULL
3. Borramos el nodo apuntado por nodo.

El paso 2 depara el nodo a borrar del resto de la lista, independientemente del nodo al que apunte Lista.

Eliminar el último nodo de una lista doblemente enlazada:

De nuevo tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->anterior.

1. Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior.
2. Hacemos que nodo->anterior->siguiente apunte a NULL
3. Borramos el nodo apuntado por nodo.

El paso 2 depara el nodo a borrar del resto de la lista, independientemente del nodo al que apunte Lista.

Eliminar un nodo intermedio de una lista doblemente enlazada:

De nuevo tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->anterior o Lista->siguiente

Se trata de un caso más general de los dos casos anteriores..

1. Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior (o Lista->siguiente).
2. Hacemos que nodo->anterior->siguiente apunte a nodo->siguiente.
3. Hacemos que nodo->siguiente->anterior apunte a nodo->anterior.
4. Borramos el nodo apuntado por nodo.

Eliminar un nodo de una lista doblemente enlazada, caso general:

De nuevo tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->anterior, si no es NULL o Lista->siguiente en caso contrario.

1. Si nodo apunta a Lista,
   • Si Lista->anterior no es NULL hacemos que Lista apunte a Lista->anterior.
   • Si Lista->siguiente no es NULL hacemos que Lista apunte a Lista->siguiente.
   • Si ambos son NULL, hacemos que Lista sea NULL.
2. Si nodo->anterior no es NULL, hacemos que nodo->anterior->siguiente apunte a nodo->siguiente.
3. Si nodo->siguiente no es NULL, hacemos que nodo->siguiente->anterior apunte a nodo->anterior.
4. Borramos el nodo apuntado por nodo.